算法系列 |
您所在的位置：网站首页 › 树的遍历 非递归 › 算法系列 |
算法系列
|
在内卷潮流的席卷下，身为算法小白的我不得不问自己，是否得踏上征程，征服这座巍巍高山。 从零开始，终点不知何方，取决于自己可以坚持多久。 希望你可以和我一样，克服恐惧，哪怕毫无基础，哪怕天生愚钝，依然选择直面困难。 分类递归 多叉树 前言在之前的文章我们学习了二叉树的遍历，顺藤摸瓜我们继续学习下多叉树的遍历。 没有看过之前二叉树遍历文章的同学可以先看看二叉树的遍历实现 算法系列-二叉树遍历 算法系列-二叉树遍历(非递归实现) 多叉树的遍历在前面二叉树的基础上，多叉树的遍历对于我们来说应该是 a piece of cake 🍰。 同样的，我们将其分为 深度优先遍历 广度优先遍历 我们下面的算法以这棵树为🌰 其数据结构表示为 const root = { data: 'A', children: [ { data: 'B', children: [ { data: 'E' }, { data: 'F', children: [ { data: "I" } ] } ] }, { data: 'C' }, { data: 'D', children: [ { data: 'G', children: [ { data: 'J' }, { data: 'K' } ] }, { data: 'H' } ] } ] } 深度优先遍历深度优先遍历和二叉树遍历非常相似，我们同样将其分为 递归实现 非递归实现 我们将在代码中通过注释进行分析，就不另外分析了 递归实现 const deepFirstSearch = (node) => { const children = node.children; console.log(node.data) if (children) { // 遍历子节点递归 for (let i = 0, len = children.length; i < len; i++) { deepFirstSearch(children[i]) } } } 非递归实现 const deepFirstSearch = (node) => { // 利用栈实现 const stack = [node] while(stack.length) { // 出栈 const curNode = stack.pop() console.log(curNode.data) // 遍历子节点压入栈中 const children = curNode.children if (children) { // 得注意这边的顺序是反向的 // 左边的节点后进栈才能先出栈 for (let len = children.length, i = len - 1; i >= 0; i--) { stack.push(children[i]) } } } } 广度优先遍历同样，广度优先遍历和二叉树遍历也非常相似，我们同样将其分为 递归实现 非递归实现 我们将在代码中通过注释进行分析，就不另外分析了 递归实现 const widthFirstSearch = (nodes) => { // 按层遍历的核心就是提前提取下次遍历的节点 const nextChildren = [] // 可以加个判断 这样就可以直接以根节点作为入参了 nodes = Array.isArray(nodes) ? nodes : [nodes] // 加判断结束递归 if (nodes.length === 0) return // 访问当前层次节点并提取下层节点 for (let i = 0, len = nodes.length; i < len; i++) { console.log(nodes[i].data) if (nodes[i].children) { nextChildren.push(...nodes[i].children) } } // 递归下层次 widthFirstSearch(nextChildren) } 非递归实现 const widthFirstSearch2 = (node) => { // 按层次遍历的非递归使用队列实现 const list = [node] // 访问当前节点的同时往队列添加子节点以待下层遍历访问 for (let i = 0; i < list.length; i++) { const curNode = list[i] console.log(curNode.data) if (curNode.children) { list.push(...curNode.children) } } } 总结在前面两篇文章二叉树的递归遍历及非递归遍历的基础下，多叉树的遍历就非常简单了。甚至多叉树的非递归遍历会比二叉树来的简单，因为不需要关注不同顺序的深度优先遍历。树的学习我们就先学到这边啦，后面我们通过leetcode的题来巩固知识。 good good staduy day day up |
【本文地址】
今日新闻 |
推荐新闻 |